namespace PF {
    type CompareFunc<T = any> = (a: T, b: T) => number;
    /**有序数组 */
    export class Heap<T> {
        private _nodes: T[];
        private _compareFunc: CompareFunc<T>;
        constructor(compareFunc?: CompareFunc<T>) {
            this._compareFunc = compareFunc || <any>defaultCmp;
            this._nodes = [];
        }

        push(n: T) {
            return Heap.push(this._nodes, n, this._compareFunc);
        }

        pop() {
            return Heap.pop(this._nodes, this._compareFunc);
        }

        peek(): T {
            return this._nodes[0];
        }

        contains(n: T) {
            return this._nodes.indexOf(n) !== -1;
        }

        replace(n: T) {
            return Heap.replace(this._nodes, n, this._compareFunc);
        }

        pushpop(n: T) {
            return Heap.pushpop(this._nodes, n, this._compareFunc);
        }

        ify() {
            return Heap.ify(this._nodes, this._compareFunc);
        }

        updateItem(n: T) {
            return Heap.updateItem(this._nodes, n, this._compareFunc);
        }

        clear() {
            this._nodes = [];
        }

        get empty() {
            return this._nodes.length === 0;
        }

        get size() {
            return this._nodes.length;
        }

        clone() {
            let heap = new Heap(this._compareFunc);
            heap._nodes = this._nodes.slice(0);
            return heap;
        }

        toArray() {
            return this._nodes.slice(0);
        }

        static push(array: any[], item: any, cmp?: CompareFunc) {
            if (cmp == null) {
                cmp = defaultCmp;
            }
            array.push(item);
            return _siftdown(array, 0, array.length - 1, cmp);
        }

        static pop(array: any[], cmp?: CompareFunc) {
            var lastelt, returnitem;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            lastelt = array.pop();
            if (array.length) {
                returnitem = array[0];
                array[0] = lastelt;
                _siftup(array, 0, cmp);
            } else {
                returnitem = lastelt;
            }
            return returnitem;
        }

        static replace(array: any[], item: any, cmp?: CompareFunc) {
            var returnitem;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            returnitem = array[0];
            array[0] = item;
            _siftup(array, 0, cmp);
            return returnitem;
        }

        static pushpop(array: any[], item: any, cmp?: CompareFunc) {
            var _ref;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            if (array.length && cmp(array[0], item) < 0) {
                _ref = [array[0], item], item = _ref[0], array[0] = _ref[1];
                _siftup(array, 0, cmp);
            }
            return item;
        }

        static ify(array: any[], cmp?: CompareFunc) {
            var i, _i, _j, _len, _ref, _ref1, _results, _results1;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            _ref1 = (function () {
                _results1 = [];
                for (var _j = 0, _ref = Math.floor(array.length / 2); 0 <= _ref ? _j < _ref : _j > _ref; 0 <= _ref ? _j++ : _j--) { _results1.push(_j); }
                return _results1;
            }).apply(this).reverse();
            _results = [];
            for (_i = 0, _len = _ref1.length; _i < _len; _i++) {
                i = _ref1[_i];
                _results.push(_siftup(array, i, cmp));
            }
            return _results;
        }

        static updateItem(array: any[], item: any, cmp?: CompareFunc) {
            var pos;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            pos = array.indexOf(item);
            if (pos === -1) {
                return;
            }
            _siftdown(array, 0, pos, cmp);
            return _siftup(array, pos, cmp);
        }

        /**查找数据集中最大的n个元素。 */
        static nlargest(array: any[], n: number, cmp?: CompareFunc) {
            var elem, result, _i, _len, _ref;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            result = array.slice(0, n);
            if (!result.length) {
                return result;
            }
            this.ify(result, cmp);
            _ref = array.slice(n);
            for (_i = 0, _len = _ref.length; _i < _len; _i++) {
                elem = _ref[_i];
                this.pushpop(result, elem, cmp);
            }
            return result.sort(cmp).reverse();
        }

        /**查找数据集中最小的n个元素。 */
        static nsmallest(array: any[], n: number, cmp?: CompareFunc) {
            var elem, i, los, result, _i, _j, _len, _ref, _ref1, _results;
            if (cmp == null) {
                cmp = defaultCmp;
            }
            if (n * 10 <= array.length) {
                result = array.slice(0, n).sort(cmp);
                if (!result.length) {
                    return result;
                }
                los = result[result.length - 1];
                _ref = array.slice(n);
                for (_i = 0, _len = _ref.length; _i < _len; _i++) {
                    elem = _ref[_i];
                    if (cmp(elem, los) < 0) {
                        insort(result, elem, 0, null, cmp);
                        result.pop();
                        los = result[result.length - 1];
                    }
                }
                return result;
            }
            this.ify(array, cmp);
            _results = [];
            for (i = _j = 0, _ref1 = Math.min(n, array.length); 0 <= _ref1 ? _j < _ref1 : _j > _ref1; i = 0 <= _ref1 ? ++_j : --_j) {
                _results.push(this.pop(array, cmp));
            }
            return _results;
        }
    }

    function defaultCmp(x: number, y: number) {
        if (x < y) {
            return -1;
        }
        if (x > y) {
            return 1;
        }
        return 0;
    }

    function _siftdown(array: any[], startpos: number, pos: number, cmp?: CompareFunc) {
        var newitem, parent, parentpos;
        if (cmp == null) {
            cmp = defaultCmp;
        }
        newitem = array[pos];
        while (pos > startpos) {
            parentpos = (pos - 1) >> 1;
            parent = array[parentpos];
            if (cmp(newitem, parent) < 0) {
                array[pos] = parent;
                pos = parentpos;
                continue;
            }
            break;
        }
        return array[pos] = newitem;
    };

    function _siftup(array: any[], pos: number, cmp?: CompareFunc) {
        var childpos, endpos, newitem, rightpos, startpos;
        if (cmp == null) {
            cmp = defaultCmp;
        }
        endpos = array.length;
        startpos = pos;
        newitem = array[pos];
        childpos = 2 * pos + 1;
        while (childpos < endpos) {
            rightpos = childpos + 1;
            if (rightpos < endpos && !(cmp(array[childpos], array[rightpos]) < 0)) {
                childpos = rightpos;
            }
            array[pos] = array[childpos];
            pos = childpos;
            childpos = 2 * pos + 1;
        }
        array[pos] = newitem;
        return _siftdown(array, startpos, pos, cmp);
    }

    function insort(a: any[], x: any, lo?: number, hi?: number, cmp?: CompareFunc) {
        var mid;
        if (lo == null) {
            lo = 0;
        }
        if (cmp == null) {
            cmp = defaultCmp;
        }
        if (lo < 0) {
            throw new Error('lo must be non-negative');
        }
        if (hi == null) {
            hi = a.length;
        }
        while (lo < hi) {
            mid = Math.floor((lo + hi) / 2);
            if (cmp(x, a[mid]) < 0) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return ([].splice.apply(a, [lo, lo - lo].concat(x)), x);
    }
}